动态DP（DDP）学习笔记

#动态DP（DDP）学习笔记| 来源: 网络整理| 查看: 265

动态DP

动态DP就是将 \(DP\) 的状态作为一个向量，\(DP\) 的转移写成一个矩阵，因为矩阵乘法的结合律，我们可以用数据结构维护矩阵的积，然后就能够支持单点修改区间查询了。

洛谷P4719 【模板】"动态 DP"&动态树分治 Description

给定一棵 \(n\) 个点的树，点带点权。

有 \(m\) 次操作，每次操作给定 \(x,y\)，表示修改点 \(x\) 的权值为 \(y\)。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

Solution

首先考虑一个朴素 \(DP\) ，设 \(dp_{u,0/1}\) 表示只考虑 \(u\) 的子树，\(u\) 没有被选/被选时的最大权独立集，有转移方程：

\[dp_{u,0}=\sum_{v\in son_u}\max(dp_{v,0},dp_{v,1})\\ dp_{u,1}=\sum_{v\in son_u}dp_{v,0} \]

现在进行树链剖分，转移时只考虑重儿子的转移，轻儿子暴力合并上来。

令

\[g_{u,0}=\sum_{v\in son_u,v\not= hson_u}\max(dp_{v,0},dp_{v,1})\\ g_{u,1}=\sum_{v\in son_u,v\not= hson_u}dp_{v,0} \]

那么

\[dp_{u,0}=g_{u,0}+max(dp_{hson_u,0},dp_{hson_u,1})\\ dp_{u,1}=g_{u,1}+dp_{hson_u,0} \]

这个转移可以写成矩阵形式：

\[\begin{bmatrix} f_{hson_u,0}\\ f_{hson_u,1} \end{bmatrix} \times \begin{bmatrix} g_{u,0}&g_{u,1}\\ g_{u,1}&-\infty \end{bmatrix} = \begin{bmatrix} f_{u,0}\\ f_{u,1} \end{bmatrix} \]

注意这里的矩阵乘法使用的是我们自定义的运算，即：

\[A\times B=C:C_{i,j}=\max_k(A_{i,k}+B_{k,j}) \]

在具体实现过程中，我们先预处理出 \(f,g\)，然后进行树链剖分，线段树维护矩阵\(\begin{bmatrix} g_{u,0}&g_{u,1}\\ g_{u,1}&-\infty \end{bmatrix}\)的乘积，查询时直接将路径上每一个链上的部分乘起来即可。

修改时，从下到上修改，\(g\) 矩阵只有轻边的顶点会被修改，在这些位置暴力修改即可。

总复杂度 \(\mathcal O(n\log^2 n)\)。

Code #include using namespace std; const int K=2; const int N=1e5+10; int n,m,a[N]; struct edge{ int v,nxt; }e[N

【本文地址】

公司简介

联系我们